#include <iostream>
#include <vector>
#include <map>
#include <string>

#define TOP true
class Value
{
public:
    enum Type{PHI};
    Value()
    {
    }
    Type type;
    std::string name;
    bool is_Value;
    bool is_VPF;
    std::string toString()
    {
        return name;
    }
};

class Statement
{
public:
    Statement(char left, char right, char oper) : left(left), right(right), oper(oper)
    {
    }
    char left;
    char right;
    char oper;
};

typedef class BasicBlock
{
public:
    BasicBlock *left, *right;
    std::vector<Statement *> stmts;
    BasicBlock()
    {
    }
    void addStatement(Statement *s)
    {
        this->stmts.push_back(s);
    }
    bool isPhi;
    int bb_no;
    int setNumber(int bb_no)
    {
        this->bb_no = bb_no;
    }
    std::string toString()
    {
        return std::to_string(bb_no) + "\n";
    }
} BB;

typedef class Partition
{
public:
    std::vector<std::vector<Value *>> partition;
    bool isTop;
    Partition()
    {
        this->isTop = false;
    }
    Partition(bool isTop) : isTop(isTop) {}

    std::string toString()
    {
        std::string res = "";
        for (auto clazz : partition)
        {
            for (auto v : clazz)
            {
                res += v->toString();
            }
            res += "\n";
        }
        return res;
    }
} P;

class CFG
{
public:
    BB *entry;
    CFG()
    {
    }
    std::map<BB *, Partition *> PIN;
    std::map<BB *, Partition *> POUT;
    std::vector<BB *> bbs;

private:
};

bool has_vn(std::vector<Value *> C) {
    for(auto v: C) {
        if(v->is_Value) {
            return false;
        }
    }
    return true;
}

bool Join(Partition *P1, Partition *P2, Partition *P)
{
    if(P1 == P2) {
        // P1 and P2 are not equal.
    } else {
        // insert the join code here.
    }
    return false;
}

bool transferFunction(Statement *s, Partition *PIN, Partition *POUT)
{
    return false;
}

void detectEquivalences(CFG &G)
{
    G.PIN.insert(std::make_pair(G.entry, new Partition()));
    for (auto bb : G.bbs)
    {
        G.POUT.insert(std::make_pair(bb, new Partition(TOP)));
        if (bb != G.entry)
        {
            G.PIN.insert(std::make_pair(bb, new Partition(TOP)));
        }
    }
    bool flag = true;
    while (flag)
    {
        flag = false;
        // POUT change
        for (auto bb : G.bbs)
        {
            if (bb == G.entry)
            {
                continue;
            }
            // only join block need this
            if(bb->isPhi) {
                Join(G.POUT.at(bb->left), G.POUT.at(bb->right), G.PIN.at(bb));
            } 
            
            for (auto s : bb->stmts)
            {
                bool temp_flag = transferFunction(s, G.PIN.at(bb), G.POUT.at(bb));
                if (flag == false && temp_flag == true)
                {
                    flag = true;
                }
            }
            // G.POUT.insert_or_assign(bb, POUT);
        }
    }
}

void dump(CFG G)
{
    std::cout << "OUTPUT:PIN===================" << std::endl;
    for (auto pair : G.PIN)
    {
        std::cout << pair.first->toString() << pair.second->toString() << std::endl;
    }
    std::cout << "OUTPUT:POUT===================" << std::endl;
    for (auto pair : G.POUT)
    {
        std::cout << pair.first->toString() << pair.second->toString() << std::endl;
    }
}

int main()
{
    CFG G;

    // test CFG;
    G.entry = new BB();
    G.bbs.push_back(G.entry);
    auto s = new Statement('a', 'b', '+');
    auto bb = new BasicBlock();
    bb->addStatement(s);
    bb->left = G.entry;
    bb->isPhi = false;
    G.bbs.push_back(bb);

    int i = 0;
    for (auto bb : G.bbs)
    {
        bb->setNumber(i++);
    }
    detectEquivalences(G);
    dump(G);
}